package farmacia.arvore;




/**
 *
 * 
 */
public class Arvore {

    private No raiz = null;
    private No a=null;
    private No b = null ;
    private boolean estouBalanceada = true;



    private void guardarValorAB(No folha) 
      {
      No aux = folha;
          while(folha.getPai()!=null && aux.getFatBal()==0)
           {
               aux=aux.getPai();
                if(aux.getFatBal()!=0)
                   {
                      a=aux;
                   }else{
                     a=null;     
                     }
           }
      }
         

    public void inserirNo(No raiz, int informacao) {         

        if (raiz == null) {

            this.raiz = criarNoArvore(informacao, null, null, null);
            
        } else {

            No noAuxiliar = raiz;
            No paiAntigo = raiz;

            while ((informacao != paiAntigo.getInfo()) && (noAuxiliar != null)) {

                paiAntigo = noAuxiliar;

                if (informacao < paiAntigo.getInfo()) {

                    noAuxiliar = paiAntigo.getFilhoEsquerdo();

                } else if(informacao > paiAntigo.getInfo()){

                    noAuxiliar = paiAntigo.getFilhoDireito();

                }

            }

            if (informacao == paiAntigo.getInfo()) {

                System.out.println("Informação Repetida");

            } else if (informacao < paiAntigo.getInfo()) {
                
                paiAntigo.setFilhoEsquerdo(criarNoArvore(informacao, paiAntigo, null, null));
                
                calcularFatBalArvore(this.raiz);
                            

                //verificarBalanceamento(paiAntigo.getFilhoEsquerdo());

            } else if (informacao > paiAntigo.getInfo()) {
                
                paiAntigo.setFilhoDireito(criarNoArvore(informacao, paiAntigo, null, null));
                
                calcularFatBalArvore(this.raiz);
                      guardarValorAB(paiAntigo.getFilhoDireito());
                //verificarBalanceamento(paiAntigo.getFilhoDireito());
            }
        }
    }

    private void rotacaoDireita(No a){

        No b, temp;
        b = a.getFilhoEsquerdo();
        temp = b.getFilhoDireito();
        b.setFilhoDireito(a);
        a.setPai(b);
        a.setFilhoEsquerdo(temp);
        if(temp!=null)
            temp.setPai(a);
        if(a.equals(this.raiz))
            this.raiz = b;
    }

    private void rotacaoEsquerda(No a){

        No b, temp;
        b = a.getFilhoDireito();
        temp = b.getFilhoEsquerdo();
        b.setFilhoEsquerdo(a);
        a.setPai(b);
        a.setFilhoDireito(temp);
        if(temp!=null)
            temp.setPai(a);
        if(a.equals(this.raiz))
            this.raiz = b;

    }

    public No criarNoArvore(int info, No pai, No f_esq, No f_dir) {

        No novoNo = new No();

        novoNo.setInfo(info);
        novoNo.setPai(pai);
        novoNo.setFilhoEsquerdo(f_esq);
        novoNo.setFilhoDireito(f_dir);
        novoNo.setFatBal(0);

        return novoNo;

    }

    public No pesquisarNo(No raiz, int informacao) {

        No paiAntigo = raiz;
        No pAuxiliar = raiz;

        while ((pAuxiliar != null) && (informacao != paiAntigo.getInfo())) {

            paiAntigo = pAuxiliar;

            if (informacao < paiAntigo.getInfo()) {

                pAuxiliar = paiAntigo.getFilhoEsquerdo();

            } else {

                pAuxiliar = paiAntigo.getFilhoDireito();
                
            }
        }

        if ((paiAntigo != null) && (paiAntigo.getInfo() == informacao)) {
            System.out.println("Informação Existente");
            return paiAntigo;
        } else {
            System.out.println("Informação Inexistente");
            return null;
        }
    }

    public void preOrdem(No raiz) {

        if (raiz != null) {
            System.out.println(raiz.getInfo() + "Fator de balanceamento: " + raiz.getFatBal());
            preOrdem(raiz.getFilhoEsquerdo());
            preOrdem(raiz.getFilhoDireito());
        }
    }

    public void posOrdem(No raiz) {

        if (raiz != null) {
            posOrdem(raiz.getFilhoEsquerdo());
            posOrdem(raiz.getFilhoDireito());
            System.out.print(raiz.getInfo() + " - ");
        }
    }

    public void emOrdem(No raiz) {

        if (raiz != null) {
            emOrdem(raiz.getFilhoEsquerdo());
            System.out.print(raiz.getInfo() + " - ");
            emOrdem(raiz.getFilhoDireito());
        }

    }

    public int calcularAltura(No raiz) {

       if (raiz == null)
          return -1; // altura de árvore vazia é -1
       else {
          int he = calcularAltura(raiz.getFilhoEsquerdo());
          int hd = calcularAltura(raiz.getFilhoDireito());
          if (he < hd)
              return hd + 1;
          else
              return he + 1;
       }

    }

    public void removeNo(int informacao) {

        No p_nodo, p_aux, orfao_esq, orfao;
        p_nodo = p_aux = this.raiz;

        //primeira fase. Encontrar a informação
        while (informacao != p_nodo.getInfo() && p_aux != null) {
            p_nodo = p_aux;
            if (informacao < p_nodo.getInfo()) {
                p_aux = p_nodo.getFilhoEsquerdo();
            } else if (informacao > p_nodo.getInfo()) {
                p_aux = p_nodo.getFilhoDireito();
            } else if (informacao == p_nodo.getInfo()) {
                p_aux = p_nodo.getPai();
            }
        }

        if (informacao == p_nodo.getInfo()) {
            if (p_nodo.getFilhoEsquerdo() == null && p_nodo.getFilhoDireito() == null) {
                if (p_aux.getFilhoEsquerdo() == p_nodo) {
                    p_aux.setFilhoEsquerdo(null);
                } else {
                    p_aux.setFilhoDireito(null);
                }
            } else if (p_nodo.getFilhoEsquerdo() == null && p_nodo.getFilhoDireito() != null) {
                p_aux.setFilhoDireito(p_nodo.getFilhoDireito());
                orfao = p_nodo.getFilhoDireito();
                orfao.setPai(p_aux);
            } else if (p_nodo.getFilhoDireito() == null && p_nodo.getFilhoEsquerdo() != null) {
                p_aux.setFilhoEsquerdo(p_nodo.getFilhoEsquerdo());
                orfao = p_nodo.getFilhoEsquerdo();
                orfao.setPai(p_aux);
            } else if (p_nodo.getFilhoDireito() != null && p_nodo.getFilhoEsquerdo() != null) {
                if (p_aux.getFilhoEsquerdo() == p_nodo) {
                    orfao_esq = p_nodo.getFilhoEsquerdo();
                    p_aux.setFilhoEsquerdo(p_nodo.getFilhoDireito());
                    //realocarNo(p_aux.getFilhoEsquerdo(), orfao_esq);
                } else {
                    orfao_esq = p_nodo.getFilhoEsquerdo();
                    p_aux.setFilhoDireito(p_nodo.getFilhoDireito());
                    //realocarNo(p_aux.getFilhoDireito(), orfao_esq);
                }
            }
        }
    }

    private void calcularFatBalArvore(No raiz){
                 boolean teste = false;
                  
        if (raiz != null)  {
            int ladoEsquerdo = calcularAltura(raiz.getFilhoEsquerdo());
            int ladoDireito = calcularAltura(raiz.getFilhoDireito());          
            
            raiz.setFatBal(ladoDireito - ladoEsquerdo);            
                   
                 if (raiz.getFatBal()>-1 && raiz.getFatBal()<1){
                           teste = false;
                       }else{
                           
teste = true;
}

            calcularFatBalArvore(raiz.getFilhoEsquerdo());
            calcularFatBalArvore(raiz.getFilhoDireito());
          return true;        
}
    }

    private boolean verificarBalanceamento(No filho){

        No A = null, B = null, temp = null;
        int info = filho.getInfo();       
        
        if (filho.getPai() != null)  {

            A = filho.getPai();
            
            while(A != null && A.getFatBal() <= 1 && A.getFatBal() >= -1){
                
                A = A.getPai();
                
            }
        }

        if(A == null)
            return false;

        else{

            if(A.getInfo() > info)
                B = A.getFilhoEsquerdo();
            else
                B = A.getFilhoDireito();
                

            if(A.getFatBal() > 0 && B.getFatBal() > 0)
                rotacaoEsquerda(A);

            else if(A.getFatBal() < 0 && B.getFatBal() < 0)
                rotacaoDireita(A);

            else if(A.getFatBal() > 0 && B.getFatBal() < 0){
                rotacaoDireita(A);
                rotacaoEsquerda(A);
            }
            else if(A.getFatBal() < 0 && B.getFatBal() > 0){
                rotacaoEsquerda(A);
                rotacaoDireita(A);

            }
        }
            return true;
    }

    public void imprimirFatBal(No raiz){
        if (raiz != null) {
            imprimirFatBal(raiz.getFilhoEsquerdo());
            imprimirFatBal(raiz.getFilhoDireito());
            System.out.println("Elemento: " + raiz.getInfo() + " Fator Balançeamento " + raiz.getFatBal());
        }
    }

    public No getRaiz() {
        return raiz;
    }

    public void setRaiz(No raiz) {
        this.raiz = raiz;
    }
}
